BinaryTree DivideAndConquer
BinaryTree DivideAndConquer
Edmend ZhangTraversal (遍历型递归)
144. Binary Tree Preorder Traversal
Description: Return the preorder traversal of a binary tree (Root → Left → Right).
Interview Thought: Think “when I arrive at this node, what should I record?” Maintain a result list. Preorder means process root first, then recurse left, then right. Traversal template applies directly.
94. Binary Tree Inorder Traversal
Description: Return the inorder traversal of a binary tree (Left → Root → Right).
Interview Thought: Standard DFS order problem. If the tree is BST, inorder gives a sorted sequence. Both recursion and stack-based iterative are common. Expectation: know both methods.
145. Binary Tree Postorder Traversal
Description: Return the postorder traversal (Left → Right → Root).
Interview Thought: Use recursion naturally, but iterative stack solution is trickier (push root-right-left, then reverse result). Interviewers may check if you understand the stack simulation.
104. Maximum Depth of Binary Tree
Description: Find the maximum depth of a binary tree.
Interview Thought: Straightforward DFS traversal: keep a global max depth counter, update at each leaf. Traversal or divide & conquer both work, but traversal (carry depth along recursion) is more natural.
Divide & Conquer (分治型递归)
257. Binary Tree Paths
Description: Return all root-to-leaf paths.
Interview Thought: Traversal: carry current path down recursion. Divide & conquer: get all paths from left and right child, prepend root value, then merge. Interviewers like traversal with backtracking.
112. Path Sum
Description: Determine if the tree has a root-to-leaf path with sum equal to target.
Interview Thought: Divide & conquer: return true if any child returns true with reduced target. Traversal also possible: carry sum downward and check at leaves.
1120. Maximum Average Subtree
Description: Find the maximum average value of any subtree.
Interview Thought: Need both sum and count of nodes from left & right subtrees. Divide & conquer: each recursion returns (sum, count), root computes average, update global max.
110. Balanced Binary Tree
Description: Check if the tree is height-balanced (height difference ≤ 1 for every node).
Interview Thought: Divide & conquer: left and right return heights; if difference > 1, propagate invalid flag. Optimize by returning -1 when imbalance detected.
236. Lowest Common Ancestor of a Binary Tree
Description: Find the lowest common ancestor of two nodes.
Interview Thought: Divide & conquer: if current node is p or q, return it. Otherwise, recurse left & right. If both sides return non-null, current node is LCA. Classic must-know pattern.
98. Validate Binary Search Tree
Description: Check if the binary tree is a valid BST.
Interview Thought: Divide & conquer: each recursion returns (min, max, valid) for subtree. Root valid if left.max < root.val < right.min. Traversal method: inorder traversal must be strictly increasing.
549. Binary Tree Longest Consecutive Sequence II
Description: Find the length of the longest consecutive path (increasing or decreasing) in the tree.
Interview Thought: Divide & conquer: each recursion returns both inc/dec length from root, parent combines left & right to compute max length.
114. Flatten Binary Tree to Linked List
Description: Flatten the tree to a linked list in-place (following preorder).
Interview Thought: Divide & conquer: flatten left & right, then rewire pointers. Iterative (Morris traversal) also possible. Key is handling root.left and root.right rearrangement.
Summary for Interview Strategy
- Traversal (路径型问题) → Think “at this node, what do I do, what do I pass down?” Often need a global variable (list, max, min).
- Divide & Conquer (返回值型问题) → Think “after I get left & right results, how do I combine?” The return value design is key.
